package leetCode.offer53;

public class Solution2 implements Solution{



    @Override
    public int search(int[] nums, int target) {
        if(nums.length==0) return 0;
        int start = 0;
        int end = nums.length-1;
        int result = 0;
        while(nums[(start+end)/2]!=target) {
            if(nums[(start+end)/2]>target){
                end = (start+end)/2-1;
                if(end<0) end = 0;
            }else if(nums[(start+end)/2]<target){
                start = (start+end)/2+1;
                if(start>nums.length-1) start = nums.length-1;
            }

            if(start==end){
                if(nums[start]==target){
                    return 1;
                }else return 0;
            }
            if(start+1==end){
                if(nums[start]==target){
                    result++;
                }
                if(nums[end]==target){
                    result ++;
                }
                return result;
            }
        }
        result++;
        int index = (start+end)/2;
        for(int i=index+1;i<nums.length;i++){
            if(nums[i]==target){
                result++;
            }else{
                break;
            }
        }
        for(int i=index-1;i>=0;i--){
            if(nums[i]==target){
                result++;
            }else{
                break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] param = {5,7,7,8,8,10};
        System.out.println(new Solution2().search(param,6));
    }

}
